package map.oj;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Num138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    //深拷贝，映射关系，通过旧的节点可以找到新的节点
    public Node copyRandomList1(Node head) {
        //1.通过遍历原链表复制新的链表，先不用管reandom
        //同时，记录一个映射关系(old —> new)
        //Node还需要具有可比较的能力，
        Map<Node,Node> map = new TreeMap<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.hashCode() - o2.hashCode();
            }
        });
        //遍历
        Node dummyHead = new Node(-1);
        Node newLast = dummyHead;

        Node current = head;
        while (current != null){
            Node newNode = new Node(current.val);

            newLast.next = newNode;
            newLast = newNode;

            //建立映射关系
            map.put(current,newNode);

            current = current.next;
        }
        //处理random的指向关系
        Node oldCurrent = head;
        Node newCurrent = dummyHead.next;
        while (oldCurrent != null){
            Node oldRandom = oldCurrent.random;
            Node newRandom = map.get(oldRandom);

            newCurrent.random = newRandom;

            oldCurrent = oldCurrent.next;
            newCurrent = newCurrent.next;
        }
        return dummyHead.next;
    }

    //138.2
    public Node copyRandomList(Node head){
        if(head == null){
            return null;
        }
        //键值对<原节点，对应新节点>
        Map<Node,Node> nodeMap = new HashMap<>();
        for (Node x = head; x != null; x = x.next) {
            Node newNode = new Node(x.val);
            nodeMap.put(x,newNode);
        }
        for (Node x = head; x != null; x = x.next){
            //通过map的key取value，取出对应的节点关系
            nodeMap.get(x).next = nodeMap.get(x.next);
            //太强了！
            nodeMap.get(x).random = nodeMap.get(x.random);
        }
        //返回也是从映射里取
        return nodeMap.get(head);
    }
}













